#include <iostream>
#include <fstream>
#include <ctime>
#include "maze.h"

mazePath::mazePath()
{
    xPos = yPos = dire = -1;
    nextStep = otherPath = NULL;
}
mazePath::~mazePath()
{}

int mazePath::stackIn(int x, int y, int d)
{
    mazePath* newStep = new mazePath;
    newStep->xPos = x;
    newStep->yPos = y;
    newStep->dire = d;
    newStep->nextStep = this->nextStep;
    this->nextStep = newStep;
    return 1;
}

int mazePath::stackOut()
{
    mazePath* tmp = this->nextStep;
    this->nextStep = this->nextStep->nextStep;
    delete tmp;
    return 1;
}

mazePath* mazePath::getTop()
{
    return this->nextStep;
}


maze::maze()
{
    for(int t1 = 0; t1 < 50; t1 ++)
        for(int t2 = 0; t2 < 50; t2 ++)
        {
            mazeMap[t1][t2] = -1;
            stepSign[t1][t2] = 0;
        }
    mapSize = 0;
    resultPath = NULL;
    finalPath = NULL;
    isMapSeted = 0;
    isSolved = 0;
    pathNum = 0;

}

maze::~maze()
{}

int maze::setMap(char *filePath)
{
    std::fstream sourceFile;
    sourceFile.open(filePath, std::ios::in);

    char tmpLine[50];
    char tmpChar;
    int size = 0;
    int mapX = 0;
    int mapY = 0;

    sourceFile >> tmpLine;
    while(sourceFile.eof() == 0)
    {

        tmpChar = tmpLine[mapY];
        if(tmpChar != '0' && tmpChar != '1')
        {
            break;
        }
        else    //if(tmpChar == '0' || tmpChar == '1')
        {
            size ++;
        }
        while(tmpChar == '0' || tmpChar == '1')
        {
            mazeMap[mapX][mapY] = tmpChar - '0';
            //std::cout << mazeMap[mapX][mapY];
            mapY ++;
            tmpChar = tmpLine[mapY];
        }
        mapY = 0;
        mapX ++;
        sourceFile >> tmpLine;
        //std::cout << std::endl;
    }

    mapSize = size;
    //std::cout << mapX << std::endl;
    sourceFile.close();

    isMapSeted = 1;
    isSolved = 0;
    initMaze();

    return 1;

}

int maze::setMap(int **newMap, int s)
{

    if(s > 50)
    {
        return 0;
    }
    int* newMapChed = (int *)newMap;
    for(int t1 = 0; t1 < s; t1 ++)
        for(int t2 = 0; t2 < s; t2 ++)
        {
            //mazeMap[t1][t2] = newMap[t1][t2];
            mazeMap[t1][t2] = *(newMapChed + t1 * s + t2);
            //mazeMap[t1][t2] = 1;
        }
    mapSize = s;

    isMapSeted = 1;
    isSolved = 0;
    initMaze();
    return 1;
}

int maze::solveMap()
{
    if(isMapSeted == 0)
    {
        return 0;
    }
    if(isSolved == 1)
    {
        return 1;
    }
    resultPath = new mazePath;
    resultPath->stackIn(1,1,1);
    stepSign[0][0] = 1;
    mazePath* pathTop = resultPath->getTop();
    while(resultPath->nextStep != NULL)
    {
        if(pathTop->xPos == mapSize && pathTop->yPos == mapSize)
        {
            savePath();
            //return 1;
            //resultPath->stackOut();
            //stepSign[mapSize - 1][mapSize - 1] = 0;
            //pathTop = resultPath->getTop();
            resultPath->stackOut();
            pathTop = resultPath->getTop();
            pathTop->dire ++;
            stepSign[mapSize - 1][mapSize - 1] = 0;
        }
        if(pathTop->dire <= 4)
        {
            switch(pathTop->dire)
            {
            case 1:
                if(pathTop->yPos + 1 <= mapSize
                        && mazeMap[pathTop->xPos - 1][pathTop->yPos + 1 - 1] == 1
                        && stepSign[pathTop->xPos - 1][pathTop->yPos + 1 - 1] == 0)
                {
                    resultPath->stackIn(pathTop->xPos, pathTop->yPos + 1, 1);
                    stepSign[pathTop->xPos - 1][pathTop->yPos + 1 - 1] = 1;
                }
                else
                {
                    pathTop->dire ++;
                }
                break;
            case 2:
                if(pathTop->xPos + 1 <= mapSize
                        && mazeMap[pathTop->xPos + 1 - 1][pathTop->yPos - 1] == 1
                        && stepSign[pathTop->xPos + 1 - 1][pathTop->yPos - 1] == 0)
                {
                    resultPath->stackIn(pathTop->xPos + 1, pathTop->yPos, 1);
                    stepSign[pathTop->xPos + 1 - 1][pathTop->yPos - 1] = 1;
                }
                else
                {
                    pathTop->dire ++;
                }
                break;
            case 3:
                if(pathTop->yPos - 1 > 0
                        && mazeMap[pathTop->xPos - 1][pathTop->yPos - 1 - 1] == 1
                        && stepSign[pathTop->xPos - 1][pathTop->yPos - 1 - 1] == 0)
                {
                    resultPath->stackIn(pathTop->xPos, pathTop->yPos - 1, 1);
                    stepSign[pathTop->xPos - 1][pathTop->yPos - 1 - 1] = 1;
                }
                else
                {
                    pathTop->dire ++;
                }
                break;
            case 4:
                if(pathTop->xPos - 1 > 0
                        && mazeMap[pathTop->xPos - 1 - 1][pathTop->yPos - 1] == 1
                        && stepSign[pathTop->xPos - 1 - 1][pathTop->yPos - 1] == 0)
                {
                    resultPath->stackIn(pathTop->xPos - 1, pathTop->yPos, 1);
                    stepSign[pathTop->xPos - 1 - 1][pathTop->yPos - 1] = 1;
                }
                else
                {
                    pathTop->dire ++;
                }
                break;
            }//switch
        }//if
        else
        {
            pathTop = resultPath->getTop();
            stepSign[pathTop->xPos - 1][pathTop->yPos - 1] = 0;
            resultPath->stackOut();
            pathTop = resultPath->getTop();
            if(pathTop != NULL)
                pathTop->dire ++;
        }
        pathTop = resultPath->getTop();
    }//while
    isSolved = 1;
    delete resultPath;
    resultPath = NULL;
    return 1;
}


int maze::printMap()
{
    if(isMapSeted == 0)
    {
        return 0;
    }
    for(int t1 = 0; t1 < mapSize; t1 ++)
    {
        for(int t2 = 0; t2 < mapSize; t2 ++)
        {
            if(mazeMap[t1][t2] == 1)
            {
                std::cout << "o";
            }
            else
            {
                std::cout << "x";
            }

        }
        std::cout << std::endl;
    }
    return 1;
}

int maze::printPath()
{
    if(isSolved == 0)
    {
        return 0;
    }
    if(pathNum == 0)
    {
        std::cout << "No Path!" << std::endl;
        return 0;
    }
    mazePath* tmpPath = finalPath;
    mazePath* tmpStep = NULL; //tmpPath->nextStep;
    for(int t1 = 1; t1 <= pathNum; t1 ++)
    {
        tmpStep = tmpPath->nextStep;
        std::cout << "Path " << t1 << ":" << std::endl;
        while(tmpStep != NULL)
        {
            std::cout << tmpStep->xPos << " "
                      << tmpStep->yPos << " "
                      << tmpStep->dire << std::endl;
            tmpStep = tmpStep->nextStep;
        }
        std::cout << std::endl;
        tmpPath = tmpPath->otherPath;
        //tmpStep = tmpPath->nextStep;

    }//for
    return 1;
}

int maze::saveMap(char *filePath)
{
    if(isMapSeted == 0)
    {
        return 0;
    }
    //fstream file1;
    //file1.open();
    std::fstream saveFile;
    saveFile.open(filePath, std::ios::out);
    for(int t1 = 0; t1 < mapSize; t1 ++)
    {
        for(int t2 = 0; t2 < mapSize; t2 ++)
        {
            saveFile << (char) (mazeMap[t1][t2] + '0');
        }
        saveFile << std::endl;
    }
    saveFile.close();
    return 1;
}

int maze::createMap(int s)
{
    if(s > 50)
    {
        return 0;
    }
    std::srand(std::time(0));
    for(int t1 = 0; t1 < s; t1 ++)
    {
        for(int t2 = 0; t2 < s; t2 ++)
        {
            mazeMap[t1][t2] = std::rand() % 2;
        }
    }
    mazeMap[0][0] = 1;
    mazeMap[s-1][s-1] = 1;
    mapSize = s;

    isMapSeted = 1;
    isSolved = 0;
    initMaze();
    return 1;

}

int maze::createRunableMap(int s, int q)
{
    if(s > 50)
    {
        return 0;
    }
    if(q >= 1 && q<= 3)
    {
        q ++;
    }
    else
    {
        q = 4;
    }
    int repeatTimes = 0;
    int oriX, oriY, isSucced = 0;
    //createMap(s);
    std::srand(std::time(0));
    int xPos = 1, yPos = 1, dir = 0;
    //stepSign[xPos-1][yPos-1] = 1;
    while(isSucced == 0)
    {
        createMap(s);
        xPos = 1;
        yPos = 1;
        dir = 1;
        stepSign[xPos-1][yPos-1] = 1;
        while(xPos != s || yPos != s)
        {
            isSucced = 1;
            if(repeatTimes >= 5)
            {
                repeatTimes = 0;
                isSucced = 0;
                break;
            }
            dir = rand() % q + 1;
            oriX = xPos;
            oriY = yPos;
            switch (dir) {
            case 1:
                if(yPos + 1 <= s && stepSign[xPos-1][yPos+1-1] == 0)
                {
                    yPos ++;
                    mazeMap[xPos - 1][yPos - 1] = 1;
                    stepSign[xPos-1][yPos-1] = 1;
                }
                break;
            case 2:
                if(xPos + 1 <= s && stepSign[xPos+1-1][yPos-1] == 0)
                {
                    xPos ++;
                    mazeMap[xPos - 1][yPos -1] = 1;
                    stepSign[xPos-1][yPos-1] = 1;
                }
                break;
            case 3:
                if(yPos - 1 >= 1 && stepSign[xPos-1][yPos-1-1] == 0)
                {
                    yPos --;
                    mazeMap[xPos - 1][yPos - 1] = 1;
                    stepSign[xPos-1][yPos-1] = 1;
                }
                break;
            case 4:
                if(xPos - 1 >= 1 && stepSign[xPos-1-1][yPos-1] == 0)
                {
                    xPos --;
                    mazeMap[xPos - 1][yPos - 1] = 1;
                    stepSign[xPos-1][yPos-1] = 1;
                }
                break;
            }//switch
            if(oriX == xPos && oriY == yPos)
            {
                repeatTimes ++;
            }
            else
            {
                repeatTimes = 0;
            }
        }//while
    }//while
    initMaze();
    return 1;
}


int maze::savePath()
{
    mazePath* tmpPath = finalPath;
    if(finalPath == NULL)
    {
        finalPath = new mazePath;
        tmpPath = finalPath;
    }
    else
    {
        while (tmpPath->otherPath != NULL)
        {
            tmpPath = tmpPath->otherPath;
        }
        tmpPath->otherPath = new mazePath;
        tmpPath = tmpPath->otherPath;
    }
    pathNum ++;

    mazePath* tmpStep = resultPath->getTop();
    while(tmpStep != NULL)
    {
        tmpPath->stackIn(tmpStep->xPos, tmpStep->yPos, tmpStep->dire);
        tmpStep = tmpStep->nextStep;
    }
    return 1;
}


int maze::initMaze()
{
    for(int t1 = 0; t1 < mapSize; t1 ++)
    {
        for(int t2 = 0; t2 < mapSize; t2 ++)
        {
            stepSign[t1][t2] = 0;
        }
    }

    mazePath *tmpPath, *tmpPathN, *tmpStep, *tmpStepN;

    tmpStep = resultPath;
    while(tmpStep != NULL)
    {
        tmpPath = tmpStep->nextStep;
        delete tmpStep;
        tmpStep = tmpPath;
    }
    resultPath = NULL;

    tmpPath = finalPath;
    while(tmpPath != NULL)
    {
        tmpPathN = tmpPath->otherPath;
        tmpStep = tmpPath->nextStep;
        while(tmpStep != NULL)
        {
            tmpStepN = tmpStep->nextStep;
            delete tmpStep;
            tmpStep = tmpStepN;
        }
        delete tmpPath;
        tmpPath = tmpPathN;
    }
    finalPath = NULL;
    pathNum = 0;
    return 1;

}

int maze::getPathNum()
{
    if(isSolved == 0)
    {
        return -1;
    }
    return pathNum;
}

int maze::getMapSize()
{
    if(isMapSeted == 0)
    {
        return -1;
    }
    return mapSize;
}

const int* maze::getMazeMap()
{
    if(isMapSeted == 0)
    {
        return NULL;
    }
    return (int *) mazeMap;
}

mazePath* maze::getFinalPath(int p)
{
    if(isSolved == 0 || p > pathNum)
    {
        return NULL;
    }

    mazePath* tmpP = finalPath;

    for(int t = 1; t < p; t ++)
    {
        tmpP = tmpP->otherPath;
    }

    return tmpP;
}


int maze::getIsSolved()
{
    return isSolved;
}

int maze::getIsMapSeted()
{
    return isMapSeted;
}
